package bloomfilter;

import com.google.common.hash.Hashing;

/**
 * @author: feiwang_6
 * @create: 2020/6/4 22:14
 * @description: Redis实现布隆过滤器
 */
public class RedisBloomFilter {
    //预计插入的元素个数
    static final int expectedInsertions = 1000;
    //期望的误判率
    static final double fpp = 0.01;
    //bit数组长度
    private static long bitSize;

    //hash函数数量
    private static int numHashFunctions;

    static {
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    public static void main(String[] args) {
        //初始化Redis布隆过滤器
/*        Jedis jedis = new Jedis("localhost", 6379);
        for (int i = 0; i < 1000; i++) {
            long[] indexArray = getIndexArray(String.valueOf(i));
            for (long index : indexArray) {
                jedis.setbit("bloom_key_name", index, true);
            }
        }
        
        //测试布隆过滤器的误报率
        int num = 0;
        for (int i = 1000; i < 2000; i++) {
            long[] indexArray = getIndexArray(String.valueOf(i));
            for (long index : indexArray) {
                if (!jedis.getbit("bloom_key_name", index)) {
                    System.out.println(i + " 一定不存在");
                    num++;
                    break;
                }
            }
        }
        System.out.println("一定不存在的有 " + num + " 个");*/
    }

    /**
     * 根据key获取布隆过滤器bitmap下标
     * (guava的布隆过滤器实现源码)
     */
    private static long[] getIndexArray(String key) {
        //低32位
        long hash1 = (int)hash(key);
        //高32位
        long hash2 = (int)(hash1 >>> 32);
        long[] result = new long[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            long combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            result[i] = combinedHash % bitSize;
        }
        return result;
    }

    /**
     * hash计算
     * @param key
     * @return
     */
    private static long hash(String key) {
        return Hashing.murmur3_128().hashBytes(key.getBytes()).asLong();
    }

    /**
     * 计算hash函数个数
     * 根据上面公式hash函数个数k = (m / n) * log(2)，需要考虑到避免因除法而截断小数部分
     *  (guava的布隆过滤器实现源码)
     * @param n
     * @param m
     * @return
     */
    private static int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    /**
     * 根据上面公式计算布隆过滤器bit数组长度m 
     *     (guava的布隆过滤器实现源码)
     * @param n
     * @param p
     * @return
     */
    private static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
}
